#include <unordered_set>
#include <vector>

using namespace std;

class Solution {
private:
    vector<vector<int>> ans;
    void dfs(unordered_set<int>& set, vector<int>& tmp) {
        if (set.empty()) {
            ans.emplace_back(tmp);
            return;
        }
        vector<int> arr(set.begin(), set.end());
        for (int& item : arr) {
            tmp.emplace_back(item);
            set.erase(item);
            dfs(set, tmp);
            set.insert(item);
            tmp.pop_back();
        }
    }
public:
    vector<vector<int>> permute(vector<int>& nums) {
        unordered_set<int> set(nums.begin(), nums.end());
        vector<int> tmp;
        tmp.reserve(nums.size());
        dfs(set, tmp);
        return ans;
    }
};